"""
例5　二分查找
1．问题描述
给定一个排序的整数数组（升序）和一个要查找的目标整数
target，查找到target第1次出现的下标（从0开始），如果target不存在于
数组中，返回-1。
2．问题示例
输入数组[1，4，4，5，7，7，8，9，9，10]和目标整数1，输出其
所在的位置为0，即第1次出现在第0个位置。输入数组[1，2，3，3，
4，5，10]和目标整数3，输出2，即第1次出现在第2个位置。输入数组
[1，2，3，3，4，5，10]和目标整数6，输出-1，即没有出现过6，返
回-1
"""


def binarySearch(array, aim):
    n = len(array)
    left = 0
    right = n - 1
    while left <= right:
        mid = (left + right) // 2
        if array[mid] > aim:
            right = mid - 1
        elif array[mid] < aim:
            left = mid + 1
        else:
            return mid
    return -1


if __name__ == '__main__':
    arr = [1, 4, 4, 5, 7, 7, 8, 9, 9, 10]
    target = 100
    print(binarySearch(arr, target))
